package ljl.alg.jianzhioffer.round2;

import commons.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 这个题不错，每次做都感觉可能做不出来
 * 越是这样，就越要做
 */
public class _07_rebuild_tree {
    
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        return rebuild(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    TreeNode rebuild(int[] preorder, int pl, int pr, int[] inorder, int il, int ir) {
        if (pl > pr) return null;
        TreeNode root = new TreeNode(preorder[pl]);
        // 找左子树长度
        int i = il;
        while (inorder[i] != preorder[pl]) {
            i++;
        }
        // pl pr, pl + 1 and leftLen .. pl +
        // il ir
        int leftLen = i - il;
        root.left = rebuild(preorder, pl + 1, pl + leftLen, inorder, il, il + leftLen - 1);
        root.right = rebuild(preorder, pl + leftLen + 1, pr, inorder, il + leftLen + 1, ir);
        return root;
    }
    
    /**
     * 路飞总是技高一筹
     * */
    int[] preorder;
    Map<Integer, Integer> inorderPos = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            inorderPos.put(inorder[i], i);
        }
        return r(0, 0, inorder.length - 1);
    }
    /**
     * 为啥这么搞？这不正好为了卡住左中右，但是 root 比较特殊，是前序的，这样方便递归？
     * 我也不知道
     * @param root 前序 root 的序号
     * @param left 中序 left 的序号
     * @param right 中序 right 的序号
     *
     * 写的时候发现，太他妈难理解了
     * */
    TreeNode r(int root, int left, int right) {
        if (left > right)
            return null;
        TreeNode res = new TreeNode(preorder[root]);
        // 这一行为啥难理解，因为绕了一个弯
        // 1. dic 是中序遍历，每个值对应的序号
        // 2. preorder[root] 是获取 root 这个序号的值
        // 也就是反过来了，获取中序遍历里，这个 root 在序号几，方便算长度
        int rootNo = inorderPos.get(preorder[root]);
        res.left = r(root + 1, left, rootNo - 1);
        // 前序，右子树的 root 在哪？root + leftLen + 1，leftLen 值为中序根位置 - left
        res.right = r(root + 1 + rootNo - left, rootNo + 1, right);
        return res;
    }
}
